package likou.jindian;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/05/23 09:25
 */
public class _16_25 {
    public static void main(String[] args) {
        _16_25 cache = new _16_25(2 /* 缓存容量 */);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

    class Node {
        int key;
        int value;
        Node next;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    Node root;
    Node tail;//指向倒数第二个元素
    int size;
    int length;

    public _16_25(int capacity) {
        root = new Node();
        tail = root;
        size = capacity;
        length = 0;
    }

    public int get(int key) {
        Node node = root.next;
        Node pre = root;
        if (node != null && node.key == key) {
            return node.value;
        }
        while (node != null && node.key != key) {
            pre = node;
            node = node.next;
        }
        if (node != null) {
            pre.next = node.next;
            node.next = root.next;
            root.next = node;
        }
        return node == null ? -1 : node.value;
    }

    public void put(int key, int value) {
        Node newNode = new Node(key, value);
        Node node = root.next;
        Node pre = root;
        if (node == null) {
            if (length < size) {
                root.next = newNode;
                length++;
            }
            return;
        }
        while (node.key != key && node.next != null) {
            pre = node;
            node = node.next;
        }
        ///找到则直接移位
        if (node.key == key) {
            pre.next = node.next;
            newNode.next = root.next;
            root.next = newNode;
            return;
        }
        //没找到，且满了
        if (length == size) {
            //移除最后一位
            pre.next = null;
            newNode.next = root.next;
            root.next = newNode;
            return;
        }
        //没找到，且还有容量
        newNode.next = root.next;
        root.next = newNode;
        length++;
    }
}
